package com.acwing.partition1;

import java.io.*;
import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/12/12 18:06
 */
public class AC6多重背包问题III {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split("\\s+");
        int n = Integer.parseInt(s[0]), capacity = Integer.parseInt(s[1]);
        int[] weight = new int[n], volume = new int[n], count = new int[n];
        for (int i = 0; i < n; i++) {
            s = reader.readLine().split("\\s+");
            weight[i] = Integer.parseInt(s[1]);
            volume[i] = Integer.parseInt(s[0]);
            count[i] = Integer.parseInt(s[2]);
        }
        writer.write(String.valueOf(dynamicProgramming1(weight, volume, count, capacity)));
        writer.flush();
    }

    private static int dynamicProgramming0(int[] weight, int[] volume, int[] count, int capacity) {
        int n = weight.length;
        int[][] dp = new int[n + 1][capacity + 1];
        int[] queue = new int[capacity + 1];
        for (int i = 1; i <= n; i++) {
            int w = weight[i - 1], v = volume[i - 1], c = count[i - 1];
            //r是把当前背包当成完全背包，并装满当前物品后，还剩余的间隙 r = capacity % v
            for (int r = 0; r < v; r ++) {
                //手动数组模拟单调队列，通过单调队列求窗口期内的最大值
                int head = 0, tail = 0;
                for (int j = r; j <= capacity; j += v) {
                    //窗口区[j-c*v,j]，队头存放窗口区的最大值，如果已经没在窗口区，就从队头移出
                    if (head != tail && queue[head] < j - c * v) head++;
                    while (head != tail && dp[i - 1][queue[tail - 1]] + (j - queue[tail - 1]) / v * w <= dp[i - 1][j]) tail--;
                    queue[tail++] = j;
                    dp[i][j] = dp[i - 1][queue[head]] + (j - queue[head]) / v * w;
                }
            }
        }
        Arrays.stream(dp).forEach(val -> System.out.println(Arrays.toString(val)));
        return dp[n][capacity];
    }

    private static int dynamicProgramming1(int[] weight, int[] volume, int[] count, int capacity) {
        int n = weight.length;
        int[] dp = new int[capacity + 1], queue = new int[capacity + 1], prev = new int[capacity + 1];
        for (int i = 1; i <= n; i++) {
            int w = weight[i - 1], v = volume[i - 1], c = count[i - 1];
            System.arraycopy(dp, 0, prev, 0, dp.length);
            for (int r = 0; r < v; r++) {
                int head = 0, tail = 0;
                for (int j = r; j <= capacity; j += v) {
                    if (head != tail && queue[head] < j - c * v) head++;
                    while (head != tail && prev[queue[tail - 1]] + (j - queue[tail - 1]) / v * w <= prev[j]) tail--;
                    queue[tail++] = j;
                    dp[j] = prev[queue[head]] + (j - queue[head]) / v * w;
                }
            }
        }
        return dp[capacity];
    }
}
